package sample.xiaosong.greedyalgorithms;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 项目利润问题
 * 输入：
 * 正数数组costs
 * 正数数组profits
 * 正数k
 * 正数m
 * 含义：
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * k表示你只能串行的最多做k个项目 m表示你初始的资金
 * 说明： 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
 * 输出： 你最后获得的最大钱数。
 */
public class IPO {

    public static class IpoNode {
        public int cost;
        public int profit;

        public IpoNode(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    public static class MinCostComparator implements Comparator<IpoNode> {

        @Override
        public int compare(IpoNode o1, IpoNode o2) {
            return o1.cost - o2.cost;
        }
    }

    public static class MaxProfitComparator implements Comparator<IpoNode> {

        @Override
        public int compare(IpoNode o1, IpoNode o2) {
            return o2.profit - o1.profit;
        }
    }

    /**
     * 贪心算法的切入点：选取利润最大的项目开始做
     *
     * 关键条件在于当前的W需要大于等于项目的花费
     * 所以需要在满足当前启动资金的情况下，选取利润最大的项目
     * 满足任意一次满足条件的选择中，均选到了利润最大的项目，就可以做到全局最优
     * @param k 一共可以做k个项目
     * @param W 启动资金W
     * @param profits 项目的利润
     * @param costs 项目的花费
     * @return 最后可以赚的钱
     */
    public static int findMaximizedCapital(int k, int W, int[] profits, int[] costs) {
        // 生成项目列表
        List<IpoNode> nodeList = new ArrayList<>();
        for (int i = 0; i < profits.length; i++) {
            nodeList.add(new IpoNode(costs[i], profits[i]));
        }
        // 项目花费小根堆
        PriorityQueue<IpoNode> minCostQ = new PriorityQueue<>(new MinCostComparator());
        // 项目利润大根堆
        PriorityQueue<IpoNode> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        minCostQ.addAll(nodeList);
        // 一共可以做k个项目
        for (int i = 0; i < k; i++) {
            // 项目花费小根堆不为空 且 第一个项目的花费小于等于启动资金
            // 将当前项目加入项目利润大根堆
            while (!minCostQ.isEmpty() && minCostQ.peek().cost <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            // 没有满足条件的项目 返回W
            if (maxProfitQ.isEmpty()) {
                return W;
            }
            // 取利润最大项目累加
            W += maxProfitQ.poll().profit;
        }
        return W;
    }

    public static void main(String[] args) {

        int[] costs = new int[]{3, 1, 2, 4, 6};
        int[] profits = new int[] {5, 3, 4, 7, 10};
        int k = 3;
        int W = 3;
        System.out.println(findMaximizedCapital(k, W, profits, costs));
    }
}
